package Algoritmos;

import grafoS.*;

/**
 * Gcol is a program to help users to learn a little about graph coloring, in
 * this software, you can learn some coloring algorithms, and add your own
 * algorithm for coloring.You can also learn BFS and DFS search. This tool, also
 * support the .col format from DIMACS (Center for Discrete Mathematics and
 * Theoretical Computer Science), so you can import a big graph and use all the
 * algorithms. Copyright (C) <2015> Clóvis Daniel Souza Silva, Samuel Silva de
 * Souza, Professor Leonardo Sampaio Rocha.
 * 
* This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
* This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
* You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * contact: projetoGrafos@gmail.com
 */

import java.util.Arrays;

/** This class extends Algotithm, so that, is built dynamically in the interface.
 * its logic consiste exchange all combinations of vertex and each make a greedy coloring
 * the best color is the best color for the graph.
 * @author Daniel
 * @author Samuel
 */
 
public class ForçaBruta extends Algorithm {

    private int cor[]; //vector of color to be used in the coloring.
    private int vetorcor[]; // vector guarding the best coloring.
    private Graph grafo; // graph to color.
    private int n; // graph vertex nuumber.
    private int numerocor; // sets the number of colors used to color the graph.
    private String patual[]; //sets current permutation.
    private int melhorcoloracao=1000000000; // sets the best coloring to the graph.
    private int[][] Grafo; //sets the adjacency matrix.
    
    /**
     *
     * @param g graph to be used in the coloring
     * @return a vector containing the color to each vertex of the graph
     */
    public int[] ReturnColor(Graph g){
        grafo = g;
        Grafo = g.getGrafo();
        n = g.getN();
        String[] vertices = new String[n];
        cor = new int[n];
        vetorcor = new int[n];
       
        for (int i = 0; i < n; i++){
            vertices[i] = Integer.toString(i);
        }
        
        patual = new String[vertices.length];
        
        permultar(vertices , 0);
        
        return vetorcor;
        
            
    }

    /**
     * This method is used to exchange a string s
     * and uses as foundation that permutation 
     * of vector s is s[1].concatenated(permultation(Aux)) so that Aux = s without s[1].
     * This method is also recursive and stops when s.leght is 1 getting so the current 
     * permutation in the vector p[]. Whith that vector p in hands it will call @see colorirBySteps(int v)
     * to color in that current permutation.
     * @param s string to be exchanged
     * @param n used to indicate what level of permutation is 
     */
    public void permultar(String s[], int n){
        //Vector with the elements that must be exchange and later combined with s[i].
        String[] Aux = new String[s.length - 1];
        int k = 0;
        
        if (s.length > 1){
            for (int i = 0; i < s.length; i++){
                for (int j = 0; j < s.length; j++){
                    if (i != j){  
                        Aux[k] = s[j];
                        k++;
                    }
                }
                k = 0;
               
                patual[n] = s[i];
                permultar(Aux, n+1);
                   
                }
                
        }else {
            numerocor=-1;
            patual[n]= s[0];
            
            for(int i=0;i<patual.length;i++){
                colorirBySteps(Integer.parseInt(patual[i]));
            }
            if(numerocor<melhorcoloracao){
             
                melhorcoloracao = numerocor;
                for(int i=0;i< patual.length;i++){
                 vetorcor[i] = cor[i]; 
                }
            }
            for (int i = 0; i < cor.length; i++){
                cor[i] = 0;
            }
            
        }

    }

    /**
     * This will check the color of adjacent vertices and assign the smallest possible color
     * to that vertex
     * @param v the to adjacent color to be checked
     */
    public void colorirBySteps(int v){
        
        
        for (int i = 0; i < n; i++){
            if (Grafo[v][i] == 1){
                if (cor[v] == cor[i] && cor[v] != 0){
                    cor[v]++;
                    i = -1;
                }
                if (cor[v] == 0){
                    cor[v]++;
                    i = -1;
                }
                if (cor[v] > numerocor){ //upgrade to graph the largest color of their vertices
                    numerocor = cor[v];
                }
            }

        }

        if (cor[v] == 0){
            cor[v]++;

        }
    }
}
